﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Ruandao.Misc
{
    /// <summary>
    /// 提供一些数学算法的工具类。
    /// </summary>
    /// <remarks>
    /// 主要方法有：<list type="bullet">
    /// <item><description>int[] IntArrayIntersection(int[] id1, int[] id2).</description></item>
    /// </list>
    /// </remarks>
    public abstract class ArithmeticKit
    {
        /// <summary>
        /// 快速计算两个整数数组的交集数据。
        /// 异常：NullArgumentException(任一个参数为空)。
        /// </summary>
        /// <param name="id1">第一个整数数组，必须是从小到大排列。</param>
        /// <param name="id2">第二个整数数组，必须是从小到大排列。</param>
        /// <returns>交集数组。</returns>
        public static int[] IntArrayIntersection(int[] id1, int[] id2)
        {
            if (id1 == null || id2 == null)
            {
                throw new ArgumentNullException("参数不能为空。");
            }

            int[] longIds;
            int[] shortIds;

            if (id1.Length < id2.Length)
            {
                shortIds = id1;
                longIds = id2;
            }
            else
            {
                shortIds = id2;
                longIds = id1;
            }

            List<int> result = new List<int>();

            int begin = 0;
            int Current = 0;
            int end = longIds.Length - 1;
            int tempend;

            foreach (int oneInShort in shortIds)
            {
                if (longIds[end] < oneInShort)
                {
                    break;
                }
                if (longIds[end] == oneInShort)
                {
                    result.Add(longIds[end]);
                    break;
                }

                tempend = end;
                while ((begin < tempend))
                {
                    Current = begin + (tempend - begin) / 2;
                    if (longIds[Current] > oneInShort)
                    {
                        if (tempend == Current) tempend--;
                        else tempend = Current;
                    }
                    else if (longIds[Current] < oneInShort)
                    {
                        if (begin == Current) begin++;
                        else begin = Current;
                    }
                    else if (longIds[Current] == oneInShort)
                    {
                        result.Add(longIds[Current]);
                        begin = Current + 1;
                        break;
                    }
                }

            }

            return result.ToArray();
        }

    }
}
